package com.cg.leetcode;

import org.junit.Test;

/**
 * 700.二叉搜索树中的搜索
 *
 * @program: LeetCode->LeetCode_700
 * @author: cg
 * @create: 2022-04-28 10:46
 **/
public class LeetCode_700 {

    @Test
    public void test700() {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(7);
        System.out.println(searchBST(root, 2));
    }

    /**
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * <p>
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     * <p>
     * 示例 1:
     * 输入：root = [4,2,7,1,3], val = 2
     * 输出：[2,1,3]
     * <p>
     * 示例 2:
     * 输入：root = [4,2,7,1,3], val = 5
     * 输出：[]
     * <p>
     * 提示：
     * 数中节点数在 [1, 5000] 范围内
     * 1 <= Node.val <= 10^7
     * root 是二叉搜索树
     * 1 <= val <= 10^7
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (val > root.val) {
            return searchBST(root.right, val);
        }
        return searchBST(root.left, val);
    }

}
